#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/6/26 9:42
# ===========================================
#       题目名称： 51. N 皇后
#       题目地址： https://leetcode.cn/problems/n-queens/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================

import copy as _cp


class Solution:

    def solveNQueens(self, n):
        cur_n = 1  # 当前第几个皇后
        const_board = [["." for y in range(n)] for x in range(n)]  # 常量棋局
        queens = []  # 所有皇后可能性
        while cur_n <= n:
            if not queens:
                for y in range(n):
                    temp_const_board = _cp.deepcopy(const_board)
                    temp_const_board[0][y] = "Q"
                    queens.append(temp_const_board)
            else:
                temp_queens = []
                for cur_queens in queens:  # 判断当前可以下棋的棋局
                    # 给当前第 cur_n 行增加皇后
                    for y in range(n):
                        is_conform = True
                        # y
                        for x in range(len(cur_queens)):
                            if "Q" == cur_queens[x][y]:
                                is_conform = False
                                break
                        # 斜线
                        # 45°
                        cur_x, cur_y = cur_n - 1, y
                        while is_conform and cur_x >= 0 and cur_y < n:
                            if cur_queens[cur_x][cur_y] == "Q":
                                is_conform = False
                                break
                            cur_x -= 1
                            cur_y += 1
                        # 135°
                        cur_x, cur_y = cur_n - 1, y
                        while is_conform and cur_x >= 0 and cur_y >= 0:
                            if cur_queens[cur_x][cur_y] == "Q":
                                is_conform = False
                                break
                            cur_x -= 1
                            cur_y -= 1
                        # 225°
                        cur_x, cur_y = cur_n - 1, y
                        while is_conform and cur_x < n and cur_y >= 0:
                            if cur_queens[cur_x][cur_y] == "Q":
                                is_conform = False
                                break
                            cur_x += 1
                            cur_y -= 1
                        # 315°
                        cur_x, cur_y = cur_n - 1, y
                        while is_conform and cur_x < n and cur_y < n:
                            if cur_queens[cur_x][cur_y] == "Q":
                                is_conform = False
                                break
                            cur_x += 1
                            cur_y += 1
                        if is_conform:
                            temp_cur_queens = _cp.deepcopy(cur_queens)
                            temp_cur_queens[cur_n - 1][y] = "Q"
                            if temp_cur_queens not in temp_queens:
                                temp_queens.append(temp_cur_queens)

                queens = temp_queens
            cur_n += 1

        return [["".join(cur_queens) for cur_queens in item] for item in queens]

    def solveNQueens2(self, n):
        """
            超出时间限制
        """
        cur_n = 1  # 当前第几个皇后
        const_board = [["." for y in range(n)] for x in range(n)]  # 常量棋局
        queens = []  # 所有皇后可能性
        while cur_n <= n:
            if not queens:  # 如果皇后棋局所有的可能性
                x, y = 0, 0  # 当前皇后可能在的位置
                while x < n:
                    y = 0  # 重置
                    while y < n:
                        temp_const_board = _cp.deepcopy(const_board)
                        temp_const_board[x][y] = "Q"
                        queens.append(temp_const_board)
                        y += 1
                    x += 1
            else:
                temp_queens = []
                for cur_queens in queens:  # 判断当前可以下棋的棋局
                    for x in range(len(cur_queens)):
                        for y in range(len(cur_queens[x])):
                            is_conform = True
                            # 检查x
                            if "Q" in cur_queens[x]:
                                is_conform = False
                            # 检查y
                            if not is_conform:
                                continue
                            for cur_board in cur_queens:
                                if cur_board[y] == "Q":
                                    is_conform = False
                                    break
                            # 斜线
                            # 45°
                            cur_x, cur_y = x, y
                            while is_conform and cur_x >= 0 and cur_y < n:
                                if cur_queens[cur_x][cur_y] == "Q":
                                    is_conform = False
                                    break
                                cur_x -= 1
                                cur_y += 1
                            # 135°
                            cur_x, cur_y = x, y
                            while is_conform and cur_x >= 0 and cur_y >= 0:
                                if cur_queens[cur_x][cur_y] == "Q":
                                    is_conform = False
                                    break
                                cur_x -= 1
                                cur_y -= 1
                            # 225°
                            cur_x, cur_y = x, y
                            while is_conform and cur_x < n and cur_y >= 0:
                                if cur_queens[cur_x][cur_y] == "Q":
                                    is_conform = False
                                    break
                                cur_x += 1
                                cur_y -= 1
                            # 315°
                            cur_x, cur_y = x, y
                            while is_conform and cur_x < n and cur_y < n:
                                if cur_queens[cur_x][cur_y] == "Q":
                                    is_conform = False
                                    break
                                cur_x += 1
                                cur_y += 1
                            if is_conform:
                                temp_cur_queens = _cp.deepcopy(cur_queens)
                                temp_cur_queens[x][y] = "Q"
                                if temp_cur_queens not in temp_queens:
                                    temp_queens.append(temp_cur_queens)
                queens = temp_queens
            cur_n += 1

        return [["".join(cur_queens) for cur_queens in item] for item in queens]


if __name__ == '__main__':
    s = Solution()
    # [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    print("n = 4 => ", s.solveNQueens(n=4))
    # [["Q"]]
    print("n = 1 => ", s.solveNQueens(n=1))
    #
    print("n = 8 => ", s.solveNQueens(n=8))
